#pragma once

#include <carbon/defs.hpp>
#include <carbon/core/detail/alloc.hpp>
#include <carbon/core/list.hpp>
#include <carbon/core/vec.hpp>

CARBON_NS_BEGIN
namespace detail {

template <typename Key,  typename Value>
struct KeyValue {
    Key     key;
    Value   value;
};

struct HashNodeBase {
    ListNodeBase  lnode;
    ListNodeBase  bnode;
    uint32_t      hashcode;
};

template <typename Key,  typename Value>
struct HashNode : public HashNodeBase {
    KeyValue<Key, Value>  data;
    HashNode() {}
    HashNode(const Key& k, const Value& v) : data{k, v} {}

    HashNode(const Key& k, Value&& v) : data{k. std::move{v}} {}
};

template <
    typename Key, 
    typename Value, 
    typename Hash,
    typename Equal,
    typename Alloc
>
struct HashTableImpl {
    using NodeType = HashNode<Key, Value>;
    using BucketVec = Vec<ListImpl, Alloc>;
    using HashFunc = Hash;
    using KeyEqual = Equal;
    using AllocType = typename Alloc::template rebind<NodeType>::other

    HashTableImpl() {}

    ~HashTableImpl() CRANE_NO_EXCEPT { this->clear(); }

    ListNodeBase * findInBucket(size_t bucket_index, uint32_t hash, const Key& key) const
    {
        ListImpl & bucket = m_buckets[bucket_index];
        ListNodeBase * p_node_base = bucket.begin();
        while ( p_node_base != bucket.end() ) {
            HashNode * p_node = static_cast<HashNode *>(p_node_base - 1);
            
            if ( p_node->hashcode == hash && m_key_equal(p_node->key, key) ) return p_node_base;
            else p_node_base = p_node_base->next;
        }

        return nullptr;
    }

    template <typename T>
    NodeType * newNode(const Key & key, T&& value, std::enable_if<std::is_same<T, Value>::value, int>::type = 0)
    {
        NodeType * node = m_alloc.allocate(1);
        m_alloc.construct(node, key, std::forward<T>(value));
        return node;
    }

    // 根据负载因子，重建buckets，逐个写入list中每个节点
    void rehash(size_t n) {
        BucketVec new_buckets(n);

        NodeType * node = m_list.begin();
        while ( node != m_list.end()) {
            size_t index = node->hashcode % new_buckets.size();
            ListImpl & bucket = new_buckets[index];
            bucket.insert(bucket.end(), &node->bnode);
            node = static_cast<NodeType *>(node->lnode.next);
        } 

        m_buckets.swap(new_buckets);
    }  // rehash

    size_t size() const { return m_list.size(); }

    size_t bucketCount() const { return m_buckets.size(); }

    NodeType *  find(const Key & key) const {
        uint32_t hash = m_hash(key);
        size_t index = hash % m_buckets.size();
        ListNodeBase * p_node = this->findInBucket(index, hash, key);
        if ( p_node == nullptr) return nullptr;
        else return static_cast<NodeType *>(p_node - 1); // bnode to node
    }

    void erase(NodeType * pnode) {
        p_node->lnode.pop();
        p_node->bnode.pop();
        m_alloc.destroy(p_node);
        m_alloc.deallocate(p_node, 1);
    }

    void clear() CRANE_NO_EXCEPT {
        for (auto & bucket : m_buckets) {
            bucket.init();
        }
        
        while ( m_list.size() != 0 ) {
            ListNodeBase * p_node_base = m_list.begin();
            p_node_base->pop();
            NodeType = p_node = static_cast<NodeType *>(p_node_base);
            m_alloc.destroy(p_node);
            m_alloc.deallocate(p_node, 1);
        }
    }

    template <typename T>
    NodeType *  insert(const Key & key, T&& value, std::enable_if<std::is_same<T, Value>::value, int>::type = 0) 
    {    
        size_t bucket_count = this->m_buckets.size();
        size_t threashold = bucket_count * m_load_factor;
        if ( this->m_size >= threshold ) this->rehash( bucket_count << 1 + 11);
        
        uint32_t hash = m_hash(key);
        size_t   index = hash % m_buckets.size();

        ListNodeBase * pnode_base = findInBucket(index, hash, key);
        if ( pnode_base ) return nullptr;  // 已经存在，不接受重复

        NodeType * p_new_node = newNode(key, std::forward<T>(value));
        m_list.insert(m_list.end(), &p_new_node->lnode);
        m_buckets[index].insert(m_buckets[index].end(), &p_new_node->bnode);

        this->rehash();
    }

    NodeType *  begin() const { return static_cast<const NodeType*>(m_list.begin()); } 
    
    NodeType *  end() const { return static_cast<const NodeType*>(&m_list.end()); }
    
    const NodeType *  cbegin() const { return static_cast<const NodeType*>(m_list.cbegin()); } 
    const NodeType *  cend() const { return static_cast<const NodeType*>(m_list.cend()); }

private:
    ListImpl        m_list;
    BucketVec       m_buckets;
    HashFunc        m_hash; 
    KeyEqual        m_equal;
    double          m_load_factor = 0.75;
    AllocType       m_alloc;
};

template<class K, class V>
struct HashTableIterator {
    HashNodeBase *  m_pnode;
    HashTableIterator() : m_pnode(nullptr)  {};

    HashTableIterator(HashNodeBase * node) : m_pnode(node) {}

    ValueType & operator*() { return static_cast<HashNode<K,V>*>(m_pnode)->data; }

    ValueType * operator->() { return &static_cast<HashNode<K,V>*>(m_pnode)->data; }
    const ValueType & operator*() const { return static_cast<HashNode<K,V>*>(m_pnode)->data; }
    const ValueType * operator->() const { return &static_cast<HashNode<K,V>*>(m_pnode)->data; }
    ListConstIterator & operator++() { m_pnode = m_pnode->lnode.next; return *this; }
    ListConstIterator & operator--() { m_pnode = m_pnode->lnode.prev; return *this; }
    ListConstIterator operator++(int) const   { auto tmp = *this; m_pnode = m_pnode->lnode.next; return tmp;  }
    RListConstIterator operator--(int) const   { auto tmp = *this; m_pnode = m_pnode->lnode.prev; return tmp;  }
    bool operator==(const ListIterator & other) const { return this->m_pnode == other.m_pnode; }
    bool operator!=(const ListIterator & other) const { return this->m_pnode != other.m_pnode; }

}; // HashTableIterator

} // detail
CARBON_NS_END

CARBON_NS_BEGIN

template<class T>
struct Result {
    T       value;
    bool    succeeded;
};


template <
    typename Key, 
    typename Value, 
    typename Hash,
    typename Equal,
    typename Alloc
>
class HashTable {
public:
    using NodeType = detail::HashTableImpl::NodeType;
    using Iterator = detail::HashTableIterator<Key, Value>;

public:
    HashTable() = default;
    ~HashTable() = default;

    bool    empty() const { return m_impl.size() == 0; }
    size_t  size()  const { return m_impl.size(); }

    Iterator find(const Key& key) { return Iterator(m_impl.find()); }

    Result<Iterator> insert(const Key& key, Value&& value) {
        auto r = m_impl.insert(key, std::move(value));
        return Result<Iterator>{Iterator(r), r != nullptr};
    }

    Result<Iterator> insert(const Key& key, const Value& value) {
        auto r = m_impl.insert(key, value);
        return Result<Iterator>{Iterator(r), r != nullptr};
    }
    
    void erase(const Key& key) CRANE_NO_EXCEPT {
        auto *pnode = m_impl.find(key);
        if ( pnode ) m_impl.erase(pnode);
    }

    void erase(Iterator it) CRANE_NO_EXCEPT {
        m_impl.erase(it.node);
    }

    void clear() { m_impl.clear(); }

    void rehash() { m_impl.rehash(); }

    Iterator begin() { return Iterator(m_impl.begin()); }
    Iterator end()   { return Iterator(m_impl.end()); }

    ConstIterator begin() const { return Iterator(m_impl.cbegin()); }
    ConstIterator end() const   { return Iterator(m_impl.cend()); }

    size_t bucketCount() const { return m_impl.bucketCount(); }

private:
    detail::HashTableImpl<Key, Value, Hash, Equal, Alloc>   m_impl;
}; // class HashTable


CARBON_NS_END
